﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>

#include<vector>
using namespace std;

//0〜n-1中缺失的数字（easy）二分查找法
//class Solution {
//public:
//    int takeAttendance(vector<int>& records) {
//        int n = records.size() - 1;
//        //if(n==records[n])   自己写的，多此一举
//            //return n+1;       只要往返回值的方向想就可以了
//        int left = 0, right = records.size() - 1;
//        while (left <= right)
//        {
//            int mid = (left + right) / 2;
//            if (records[mid] == mid)
//            {
//                left = mid + 1;
//            }
//            else
//            {
//                right = mid - 1;
//            }
//        }
//        return left;
//    }
//};

//前缀和   
//#include <iostream>
//#include<vector>
//using namespace std;
//
//int main() {
//    int n, q;
//    cin >> n >> q;
//    //arr存储数据
//    vector<int> arr(n + 1);
//    for (int i = 1; i <= n; i++) cin >> arr[i];
//
//    //前缀和 
//    vector<long long> sum(n + 1);
//    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + arr[i];
//
//    //计算结果
//    int l, r;
//    while (q--)
//    {
//        cin >> l >> r;
//        cout << sum[r] - sum[l - 1] << endl;
//    }
//    return 0;
//}
//// 64 位输出请用 printf("%lld")

